The present invention relates generally to hashing algorithms, and in particular, to universal hashing algorithms for Plaintext aware encryption.
Cryptographic systems are known in the data processing art. In general, these systems operate by performing an encryption operation on a Plaintext input message by using an encryption key and a symmetric key block cipher, and producing a Ciphertext message. The encrypted message may then be stored on an insecure device. The stored message may be decrypted with the corresponding decryption operation using the same key, to recover the Plaintext message. Since the same key is used for both the Encryption and decryption of the message, the process is referred to as a “symmetric key” process.
Although the above encryption hides the Plaintext from an adversary, one may want to store data in an insecure and/or unreliable device and later check to determine if the data was not deliberately or accidentally modified. To this end, a universal hash of the data is computed. Since the hash is a comparatively small piece of data relative to the data stored, the user will store the data and save the hash in a secure location to prevent stored data modification. When retrieving the data at a later time, the user would regenerate the hash on the retrieved data, and compare it with the original hash for authenticity. Here, “universal hash” refers to the fact that the hash is key dependent, with the further property that the probability is extremely small that two messages, whether random or generated by someone who is not privy to the key of the hash, will hash to the same value.
If a Ciphertext consists of several blocks, a universal hash is usually constructed by a chaining mechanism, which is inherently sequential. There are alternative methods such as a universal message authentication code (“UMAC”), which, however, require a large amount of key material.
Accordingly, what is needed is a universal hash for Plaintext-aware encryption that has low-complexity and does not require a large amount of key material.